package com.hackerrank.challenges.sudoku;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Solution {
	private static class Sudoku {
		Set<Integer>[][] p, rowNum, colNum, groupNum;
		int size, groupRows, groupCols;
		private static class RowCol {
			int r, c;
			public RowCol(int r, int c) {
				this.r = r;
				this.c = c;
			}
		}
		private static class Group {
			int g, gi;
			public Group(int g, int gi) {
				this.g = g;
				this.gi = gi;
			}
		}
		private Sudoku() {
		}
		/**
		 * @param groupRows number of rows in each group
		 * @param groupCols number of columns in each group
		 */
		public Sudoku(int groupRows, int groupCols) {
			this.size = groupRows * groupCols;
			this.groupRows = groupRows;
			this.groupCols = groupCols;
			Set<Integer> l = new HashSet<Integer>();
			for(int i = 1; i <= size; i++)
				l.add(i);
			p = new HashSet[size][];
			for(int r = 0; r < size; r++) {
				p[r] = new HashSet[size];
				for(int c = 0; c < size; c++) {
					p[r][c] = new HashSet<Integer>();
					p[r][c].addAll(l);
				}
			}
			// initialize rowNum
			rowNum = new HashSet[size][];
			for(int r = 0; r < size; r++) {
				rowNum[r] = new HashSet[size + 1];
				for(int n = 0; n <= size; n++) {
					rowNum[r][n] = new HashSet<Integer>();
					for(int i = 0; i < size; i++)
						rowNum[r][n].add(i);
				}
			}
			// initialize colNum
			colNum = clone(rowNum);
			// initialize groupNum
			groupNum = clone(rowNum);
		}
		private boolean remove(RowCol rc, Integer n) {
			Group g = getGroup(rc);
			if(!p[rc.r][rc.c].contains(n))
				return true;
			p[rc.r][rc.c].remove(n);
			rowNum[rc.r][n].remove(rc.c);
			if(rowNum[rc.r][n].size() == 1) {
				if(!set(new RowCol(rc.r, rowNum[rc.r][n].iterator().next()), n))
					return false;
			} else if(rowNum[rc.r][n].size() == 0)
				return false;
			colNum[rc.c][n].remove(rc.r);
			if(colNum[rc.c][n].size() == 1) {
				if(!set(new RowCol(colNum[rc.c][n].iterator().next(), rc.c), n))
					return false;
			} else if(colNum[rc.c][n].size() == 0)
				return false;
			groupNum[g.g][n].remove(g.gi);
			if(groupNum[g.g][n].size() == 1) {
				if(!set(getRowCol(new Group(g.g, groupNum[g.g][n].iterator().next())), n))
					return false;
			} else if(groupNum[g.g][n].size() == 0)
				return false;
			if(p[rc.r][rc.c].size() == 1) {
				if(!set(new RowCol(rc.r, rc.c), p[rc.r][rc.c].iterator().next()))
					return false;
			} else if(p[rc.r][rc.c].size() == 0)
				return false;
			return true;
		}
		private Group getGroup(RowCol rc) {
			int ng = size / groupCols; // number of groups in each row
			int gr = rc.r / groupRows, gc = rc.c / groupCols;
			int dr = rc.r - gr * groupRows, dc = rc.c - gc * groupCols;
			return new Group(gr * ng + gc, dr * groupCols + dc);
		}
		private RowCol getRowCol(Group g) {
			int ng = size / groupCols; // number of groups in each row
			int gr = g.g / ng, gc = g.g % ng;
			return new RowCol(gr * groupRows + g.gi / groupCols, gc * groupCols + g.gi % groupCols);
		}
		private boolean set(RowCol rc, Integer n) {
			if(!p[rc.r][rc.c].contains(n))
				return false;
			if(p[rc.r][rc.c].size() > 1) {
				for(int i = 1; i < n; i++)
					if(!remove(rc, i))
						return false;
				for(int i = n + 1; i <= size; i++)
					if(!remove(rc, i))
						return false;
				return true;
			}
			// remove n from all group cells
			int il = (rc.r / groupRows + 1) * groupRows, jl = (rc.c / groupCols + 1) * groupCols;
			for(int i = (rc.r / groupRows) * groupRows; i < il; i++) {
				for(int j = (rc.c / groupCols) * groupCols; j < jl; j++) {
					if(i != rc.r || j != rc.c)
						if(!remove(new RowCol(i, j), n))
							return false;
				}
			}
			// remove n from row
			for(int j = 0; j < rc.c; j++)
				if(!remove(new RowCol(rc.r, j), n))
					return false;
			for(int j = rc.c + 1; j < size; j++)
				if(!remove(new RowCol(rc.r, j), n))
					return false;
			// remove n from column
			for(int i = 0; i < rc.r; i++) {
				if(!remove(new RowCol(i, rc.c), n))
					return false;
			}
			for(int i = rc.r + 1; i < size; i++)
				if(!remove(new RowCol(i, rc.c), n))
					return false;
			return true;
		}
		private static Set<Integer>[][] clone(Set<Integer> a[][]) {
			Set<Integer> cln[][] = new HashSet[a.length][];
			for(int i = 0; i < a.length; i++) {
				cln[i] = new HashSet[a[i].length];
				for(int j = 0; j < a[i].length; j++) {
					cln[i][j] = new HashSet<Integer>();
					cln[i][j].addAll(a[i][j]);
				}
			}
			return cln;
		}
		public Sudoku clone() {
			Sudoku cln = new Sudoku();
			cln.size = size;
			cln.groupRows = groupRows;
			cln.groupCols = groupCols;
			cln.p = clone(p);
			cln.rowNum = clone(rowNum);
			cln.colNum = clone(colNum);
			cln.groupNum = clone(groupNum);
			return cln;
		}
		private Sudoku solve(RowCol rc) {
			if(rc.r >= p.length)
				return this;
			for(int v : p[rc.r][rc.c]) {
				Sudoku cln = clone();
				if(cln.set(rc, v)) {
					int nr = rc.r, nc = rc.c + 1;
					nr += nc / size;
					nc %= size;
					Sudoku sol = cln.solve(new RowCol(nr, nc));
					if(sol != null)
						return sol;
				}
			}
			return null;
		}
		public String toString() {
			StringBuilder sb = new StringBuilder();
			for(int r = 0; r < size; r++) {
				for(int c = 0; c < size; c++)
					sb.append(p[r][c].iterator().next()).append(" ");
				sb.append("\n");
			}
			return sb.toString();
		}
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int t = 0; t < T; t++) {
			Sudoku sudoku = new Sudoku(3, 3);
			for(int r = 0; r < sudoku.size; r++)
				for(int c = 0; c < sudoku.size; c++)
					sudoku.set(new Sudoku.RowCol(r, c), Integer.valueOf(in.nextInt()));
			System.out.println(sudoku.solve(new Sudoku.RowCol(0, 0)));
		}
	}
}
